\documentclass[twoside,a4paper]{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{NAME Jiatu Yan }
\chead{NumericalODE/PDE homework \#1}
\rhead{Date 2021.4.3}


\section*{Exercise 7.9 Verify that (7.7) is indeed a norm in the sense of Definition B.84.}
Assume set $A = \{M:\forall x\in\mathrm{F}^{n},  \mid Tx \mid \le M \mid x \mid \}$.

\subsection*{(NRM-1)} 
$\forall T\in\mathcal{L}\left( \mathbb{F}^{n}, \mathbb{`F}^{m} \right) $, let $x = e$, then we have 
	\[ 0\le  \mid Tx \mid = \mid Te \mid \le M \mid e \mid=M. \]
As $ M\ge 0$, we have \[ \mid  \mid T \mid  \mid =\inf_{M\in A} M\ge 0.\]

\subsection*{(NRM-2)}
If $T\neq 0$, we have\[\exists  \epsilon>0, x\in\mathbb{F}^{n},\mid x \mid =1,s.t.  \mid Tx \mid >\epsilon>0.\]
So there is \[\forall M\in A,s.t.\epsilon < \mid Tx \mid \le M \mid x \mid .\]
Which means \[ \mid  \mid T \mid  \mid =\inf_{M\in A}M>\epsilon>0.\]
If $T=0$, we have \[\forall x\in\mathbb{F}^{n}, \mid Tx \mid =0\le 0\cdot \mid x \mid .\]
\[\forall \epsilon>0, \mid Tx \mid =0>\left( 0 - \epsilon \right)\cdot  \mid x \mid  .\]
So $0 = \inf_{M\in A}M =  \mid  \mid T \mid  \mid .$
Thus $ \mid  \mid T \mid  \mid =0\Rightarrow T=0.$

\subsection*{(NRM-3)}
$\forall T\in\mathcal{L}\left( \mathbb{F}^n, \mathbb{F}^m \right)$, assume $  \mid  \mid T \mid  \mid = a$.

If $a=0$, which means $T = 0$. It is obvious that  $\forall \alpha\in\mathbb{F},  \mid  \mid \alpha T \mid  \mid =
 \mid \alpha \mid \cdot \mid  \mid T \mid  \mid $.

 If $a\neq 0$, $\forall \alpha\in\mathbb{F}$, we have
 \begin{equation*}
 	\begin{split}
		\mid  \mid \alpha T \mid  \mid &=\inf \{M: \mid \alpha Tx \mid \le M\cdot \mid x \mid , \forall x\in\mathbb{F}^n\}\\
					       &=\inf\{M: \mid \alpha \mid\cdot \mid Tx \mid \le M\cdot  \mid x \mid ,\forall x\in\mathbb{F}^{n} \}\\
					       &=\inf\{M: \mid Tx \mid \le \frac{M}{ \mid \alpha \mid } \mid x \mid ,\forall x\in\mathbb{F}^{n}\}\\ 
 	\end{split}
 \end{equation*}
 So  \[
 \frac{ \mid \mid  \alpha T \mid  \mid }{ \mid \alpha \mid } =a \Rightarrow  \mid  \mid \alpha T \mid  \mid = \mid \alpha \mid a
 = \mid \alpha \mid \cdot \mid  \mid T \mid  \mid 
 .\]

 \subsection*{(NRM-4)}
 $\forall T_1, T_2\in \mathcal{L}\left( \mathbb{F}^n, \mathbb{F}^m \right) $, $\forall x\in\mathbb{F}^n$.
 By \[
	 \mid \left(T_1 - T_2  \right)x \mid \le  \mid T_1x \mid  +  \mid T_2x \mid \le
	 	 \left(  \mid  \mid T_1 \mid  \mid  +  \mid  \mid T_2 \mid  \mid  \right)x 
 .\] 
So
 \[
	 \left(  \mid \mid T_1 \mid  \mid + \mid  \mid T_2 \mid  \mid   \right) \in
	 \{M: \mid  \mid \left( T_1+T_2 \right)x \mid  \mid \le M \mid  \mid x \mid  \mid ,\forall x\in\mathbb{F}^n \}
.\] 
Thus, we have
\[
	\mid  \mid T_1+T_2 \mid  \mid =\inf\{M:\mid  \mid \left( T_1+T_2 \right)x \mid  \mid \le
	M \mid  \mid x \mid  \mid ,\forall x\in\mathbb{F}^n \}\le  \mid  \mid T_1 \mid  \mid + \mid  \mid T_2 \mid  \mid 
.\] 


So we proved that (7.7) is a norm.
\section*{Exercise 7.14 Verify that the space $\mathcal{L}\left( \mathbb{F}^n, \mathbb{F}^m \right)$ becomes a metric space if we define the metric as $d\left( T,S \right)= \mid  \mid T-S \mid  \mid  $.}

\subsection*{(1) Non-negativity}
This is easily achieved by
\[
	d\left( T,S \right)= \mid  \mid T-S \mid  \mid =sup_{ \mid x \mid =1} \mid \left( T-S \right)x \mid \ge 0 
.\]
\subsection*{(2) Identity of indiscernibles}
If $T=S$, which means $T-S=0$.It is obvious that $d\left( T,S \right)= \mid  \mid T-S \mid  \mid=0  $. 

\subsection*{(3) Symmetry}
$\forall T,S\in \mathcal{L}\left( \mathbb{F}^{n}, \mathbb{F}^{m} \right) $, we have
\[
	d\left( T,S \right) = \mid  \mid T-S \mid  \mid = \mid  \mid \left( -1 \right) \left( S-T \right)  \mid  \mid =
	\mid -1 \mid \cdot\mid  \mid S-T \mid  \mid = \mid  \mid S-T \mid  \mid =d\left( S,T \right)  
.\]

\subsection*{(4) Triangle inequality}
$\forall T,S,R \in \mathcal{L}\left( \mathbb{F}^{n},\mathbb{F}^{m} \right) $, we have 
\begin{equation*}
	\begin{split}
		d\left( T,S \right)= \mid  \mid T-S \mid  \mid = \mid  \mid T-R+R-S \mid  \mid 
		&=\sup_{ \mid x \mid =1} \mid\left[ \left( T-R \right)+\left( R-S \right) \right]x\mid \\
		&\le \sup_{ \mid x \mid =1}\left[ \mid \left( T-R \right)x \mid + \mid \left( R-S \right)x \mid \right]\\  
		&\le \sup_{ \mid x \mid =1} \mid \left(  T-R \right)x \mid +\sup_{ \mid x \mid =1} \mid \left(R-S  \right)x \mid\\
		&= \mid  \mid T-R \mid  \mid + \mid  \mid R-S \mid  \mid \\
		&=d\left( T,R \right)+d\left( R,S \right)  
	\end{split}
\end{equation*}

Thus $d\left( T,S \right)= \mid  \mid T-S \mid  \mid  $ defines a metric.

\section*{Exercise 7.15 Prove the range of T is contained in $\mathbb{R}^n$, and $ \mid  \mid T \mid  \mid 
=\sup_{ \mid x \mid <=1,x\in\mathbb{R}^n} \mid Tx \mid =\sup_{ \mid z \mid <=1,z\in\mathbb{C}^n} \mid Tz \mid $.}
$\forall x\in\mathbb{R}^{n}$, we can find a set of real numbers $\{\alpha_i\}_n$ 
that satisfies  $x=\sum_{i=1}^{n}\alpha_ie_i$. Then we have $T\left( x \right)=\sum_{i=1}^{n}\alpha_iTe_i\in \mathbb{R}^m $,
as each $Te_i\in \mathbb{R}^m$.

By the definition of the linear map $T\in\mathcal{L}\left( \mathbb{C}^n,\mathbb{C}^m \right) $ 
,we have $T\left( a+ib \right) =T\left( a \right)+iT\left( b \right)  ,\forall a,b\in\mathbb{R}^n$.
Assume $e_a = a/  \mid a \mid , e_b = b / \mid  b\mid $.
It is obvious that

\[ 
	\mid \mid T \mid \mid =sup_{ \mid a \mid =1} \mid Tx \mid = sup_{z=a,  \mid a \mid =1} \mid Tz \mid 
	\le \sup_{ \mid z \mid \le 1} \mid Tz \mid  
.\] 
\begin{equation*}
	\begin{split}
		\forall z\in\mathbb{C}^n, &Z=a+ib, a,b\in\mathbb{R}^n.\\
		\sup_{ \mid z \mid \le 1} \mid Tz \mid 
		&=\sup_{ \mid a \mid^2 + \mid b \mid^2\le 1 } \mid Ta+iTb \mid \\
		&=\sup_{ \mid a \mid ^2+ \mid b \mid ^2\le 1}\left(  \mid Ta \mid ^2 + \mid Tb \mid ^2\right)^{1 /2}\\
		&=\sup_{ \mid a \mid ^2+ \mid b \mid ^2\le 1}\left(  \mid a \mid^2  \mid Te_a \mid ^2+ \mid b \mid ^2 \mid Te_b \mid ^2 \right)^{1 /2}\\ 
		&\le \sup_{ \mid a \mid^2 +  \mid b \mid^2  \le 1} \left(  \mid a \mid ^2+ \mid b \mid ^2 \right)  \mid \mid T \mid \mid  \\
		&= \mid \mid  T  \mid  \mid. \\
	\end{split}
\end{equation*}
Thus we have $ \mid  \mid T \mid  \mid =\sup_{ \mid a \mid \le 1} \mid Ta \mid = \sup_{ \mid z \mid \le 1} \mid Tz \mid $.

\section*{Exercise 7.17 Verify that (7.10) is indeed a norm in the sense of Definition B.84.}
\subsection*{(NRM-1)}
$\forall T\in\mathcal{L}\left( \mathbb{F}^n, \mathbb{F}^m \right) $, we can easily have
\[
	\mid T \mid := \left( \sum_{j=1}^{n} \mid Te_j \mid^2 \right)^{1 /2}\ge 0 
.\]
\subsection*{(NRM-2)}
if $ \mid T \mid =0$, we have
 \begin{equation*}
	 \begin{split}
		 \mid T \mid =0&\Rightarrow \left( \sum_{j=1}^{n} \mid Te_j  \mid ^2\right)^{1 /2}=0\\
			     &\Rightarrow  \mid Te_j \mid =0, \forall j\in\{1\ldots n\}\\
			     &\Rightarrow Te_j=0, \forall  j\in\{1\ldots n\}\\
			     &\Rightarrow T=0.
	 \end{split}
 \end{equation*}

 \subsection*{(NRM-3)}
 $\forall a\in\mathbb{F}, T\in\mathcal{L}\left( \mathbb{F}^n, \mathbb{F}^m \right) $, we have
 \begin{equation*}
 	\begin{split}
		\mid aT \mid&=\left( \sum_{j=1}^{n} \mid aTe_j \mid ^2 \right)^{1 /2}\\
			    &=\left(\sum_{j=1}^{n} \mid a \mid ^2 \mid Te_j \mid ^2  \right)^{1/ 2}\\ 
			    &=\left(  \mid a \mid ^2 \right)^{1 /2}\left( \sum_{j = 1}^{n} \mid Te_j \mid ^2 \right)^{1 /2}\\
			    &= \mid a \mid \cdot \mid T \mid .
 	\end{split}
 \end{equation*}

 \subsection*{(NRM-4)}
 $\forall T,S\in \mathcal{L}\left( \mathbb{F}^n, \mathbb{F}^m \right) $, we have
 \begin{equation*}
 	\begin{split}
		\mid T+S \mid &=\left( \sum_{j=1}^{n} \mid \left( T+S \right)e_j  \mid ^2 \right)^{1 /2}\\ 
			      &=\left( \sum_{j=1}^n \mid Te_j+ Se_j\mid^2  \right)^{1 /2}\\
			      &\le \left( \sum_{j=1}^{n} \mid Te_j |^2\right) ^{1 /2}+\left( \sum_{j=1}^{n} \mid Se_j \mid ^2 \right)^{1 /2}\\
			      &= \mid T \mid + \mid S \mid . 
 	\end{split}
 \end{equation*}
 The first inequality is achieved by Minkowski inequality.

 Thus (7.10) is a norm.

 \section*{Exercise 7.21 Prove Corollary 7.20 $ \mid TS \mid \le  \mid T \mid  \mid S \mid $.}

 $\forall T,S\in\mathcal{L}\left( \mathbb{F}^n,\mathbb{F}^m \right) $, we have
\begin{equation*}
	\begin{split}
		\mid TS \mid &=\left( \sum_{j=1}^{n} \mid TSe_j \mid ^2 \right)^{1 /2}\\
			     &\le \left( \sum_{j=1}^{n}\left(  \mid T \mid \cdot \mid Se_j \mid  \right)^2  \right)^{1 /2}\\
			     &= \mid T \mid \cdot\left( \sum_{j=1}^{n} \mid Se_j \mid ^2 \right)^{1 /2}\\
			     &= \mid T \mid  \mid S \mid. 
	\end{split}
\end{equation*}

\section*{Exercise 7.38 Prove Theorem 7.37 det$e^{X}=e^{\mathrm{Trace}X}$.}
$\forall X\in\mathbb{C}^{n\times n}$, we can seperate $X$ by $X=L+\Lambda+U$
, where all the elements of $L$ lying on and over the diagnal are zero and those of $U$ lying on and below diagonal are zero on $U$.
$X=\mathrm{diag}{x_{11},\ldots,x_{nn}}$. Then by Lemma 7.28 we have
\[
	\mathrm{det}e^{x}=\mathrm{det}e^{L+\Lambda+U}=\mathrm{det}\left(e^{L}e^{\Lambda}e^{U}\right)
.\] 
By Definition 7.25
\[
	e^{L}=I+\sum_{i=0}^{\infty}\frac{1}{i!}L^{i}
.\] 
So the elements on the diagonal of L are 1 and the elements over the diagonal of L are zero. So det$e^{L}=1$. Similarly, we have det$e^{U}=1$.
Thus we have
\begin{equation*}
	\begin{split}	
		\det e^{X}&=\det\left( e^{L} \right)\det\left( e^{\Lambda} \right)\det\left( e^{U} \right)\\
	&=\det e^{\Lambda}\\
	&=\det\left( I+\sum_{i=1}^{\infty}\frac{1}{i!}\Lambda^{i} \right)\\
	&=\det\left( \mathrm{diag}{\sum_{j=0}^{\infty}\frac{1}{j!}x_{11}^{j},\ldots,
	\sum_{j=0}^{\infty}\frac{1}{j!}x_{nn}^{j}} \right)\\
	&=\det\left( e^{x_{11}},\ldots,e^{x_{nn}} \right) \\
	&=e^{\sum_{i=1}^{n}x_{ii}}\\
	&=e^{\mathrm{Trace{X}}}.
	\end{split}
\end{equation*}

\section*{Exercise 7.57 Show the matrix with the characteristic polynomial $p_M\left( z \right)=z^{s}+\sum_{j=0}^{s-1}\alpha_jz^{j} $.}
Assume the matrix
\begin{equation*}
	A_i =
	\left[
	\begin{array}{c c c c c}
		\lambda& -1& 0& \ldots&0\\ 
		0& \lambda& -1& \ldots& 0\\
		\ldots&\ldots&\ldots&\ldots&\ldots\\
		\alpha_0&\alpha_1&\alpha_2&\ldots&\alpha_{i-1}\\
\end{array}\right]_{i\times i}.
\end{equation*}
We can deduce that
\begin{equation*}
	\det\left(A_i  \right)=\alpha_{i-1}\lambda^{i-1}+\left( -1 \right)^2\det\left( A_{i-1} \right). 
\end{equation*}
So we have
\begin{equation*}
	\begin{split}
		det\left( \lambda I - M \right)&=\left( \lambda+\alpha_{s-1} \right)\cdot\lambda^{s-1} 
		+ \left( -1 \right)^2\cdot\det\left( A_{s-1} \right)\\
					       &=\lambda^{s}+\alpha_{s-1}\lambda^{s-1}+\alpha_{s-2}\lambda^{s-2}+det\left(A_{s-2}  \right)\\
					       &\ldots\\
					       &=\lambda^{s} +\sum_{j=0}^{s-1}\alpha_j\lambda^{j}\\
					       &=p_M\left( \lambda \right) .
	\end{split}
\end{equation*}
So we have proved that $p_M\left( z \right) $ is the characteristic polynomial of $M$.

\section*{Exercise 7.110 Compute the first five coefficients $C_j$'s of the trapezoidal rule and the midpoint rule from Examples 7.96 and 7.98.}
\subsection*{Trapezoidal rule}
For trapezoidal rule, we know that $s=1, \alpha_1=1,\alpha_0=-1,\beta_1=\beta_0=1 /2$.
Then we can calculate the coefficients.
\begin{equation*}
	\begin{split}
		C_0&=\alpha_1+\alpha_0=0\\
		C_1&=0\alpha_0-\beta_0+1\alpha_1-1\beta_1=\frac{1}{2}\\
		C_2&=\sum_{i=0}^{1}\left( \frac{1}{2!}i^{2}\alpha_i-1i^{1}\beta_i \right)\\
		   &=\frac{1}{2!}\alpha_1-\beta_1=0\\
		C_3&=\sum_{i=0}^{1}\left( \frac{1}{3!}i^{3}\alpha_i-\frac{1}{2!}i^{2}\beta_i \right)\\
		   &=\frac{1}{3!}\alpha_1-\frac{1}{2!}\beta_1=-\frac{1}{12}\\   
		C_4&=\sum_{i=0}^{1}\left( \frac{1}{4!}i^{4}\alpha_i-\frac{1}{3!}i^{3}\beta_i \right)\\
		   &=\frac{1}{4!}\alpha_1-\frac{1}{3!}\beta_1=-\frac{1}{24}\\
	\end{split}
\end{equation*}

\subsection*{Midpoint rule}
For midpoint rule, we know that $s=2, \alpha_0=-1,\alpha_1=0,\alpha_2=1,\beta_0=\beta_2=0, \beta_1=2 $.
Then we can calculate the coefficients.
\begin{equation*}
	\begin{split}
		C_0&=\alpha_2+\alpha_1 + \alpha_0=0\\
		C_1&=-\beta_0+\alpha_1-\beta_1+2\alpha_2-\beta_2=0\\
		C_2&=\sum_{i=0}^{2}\left( \frac{1}{2!}i^{2}\alpha_i-1i^{1}\beta_i \right)\\
		   &=\frac{1}{2!}\alpha_1-\beta_1 + \frac{1}{2!}2^{2}\alpha_2-2\beta_2=0\\
		C_3&=\sum_{i=0}^{2}\left( \frac{1}{3!}i^{3}\alpha_i-\frac{1}{2!}i^{2}\beta_i \right)\\
		   &=\frac{1}{3!}\alpha_1-\frac{1}{2!}\beta_1 +  \frac{1}{3!}2^{3}\alpha_2- \frac{1}{2!}2^{2}\beta_2
		   =\frac{1}{3}\\   
		C_4&=\sum_{i=0}^{2}\left( \frac{1}{4!}i^{4}\alpha_i-\frac{1}{3!}i^{3}\beta_i \right)\\
		   &=\frac{1}{4!}\alpha_1-\frac{1}{3!}\beta_1 + \frac{1}{4!}2^{4}\alpha_2-\frac{1}{3!}2^{3}\beta_2
		   =\frac{1}{3}\\
	\end{split}
\end{equation*}	

\section*{Exercise 7.112 Express conditions of $\mathcal{L}=\mathrm{O}\left( k^{3} \right) $ using characteristic polynomials.}
The necessary condition for $ \mid  \mid \mathcal{L}u\left(t_n  \right) \mid  \mid =\mathrm{O}\left( k^{3} \right)  $ is $C_0=C_1=C_2=0$ 
, which means that
 \begin{equation*}
	\begin{split}
		C_0&=\sum_{j=0}^{s}\alpha_j=0\\
		C_1&=\sum_{j=0}^{s}\left( j\alpha_j-\beta_j \right)i=0\\
		C_2&=\sum_{j=0}^{s}\left( \frac{1}{2}j^2\alpha_j-j\beta_j \right)=0.\\ 
	\end{split}
\end{equation*}

By characteristic polynomials $\rho\left( z \right)=\sum_{j=0}^{s}\alpha_jz^{j} $ 
and $\sigma\left( z \right)=\sum_{j=0}^{s}\beta_jz^{j} $, we have
\begin{equation*}
	\begin{split}
		C_0=0&\Rightarrow\rho\left( 1 \right)=0\\
		C_1=0&\Rightarrow\rho'\left( 1 \right)-\sigma\left( 1 \right)=0\\
		C_2=0&\Rightarrow\rho''\left( 1 \right)-\sigma'\left( 1 \right)=0.\\  
	\end{split}
\end{equation*}

The equations above are the conditions of $\mathcal{L}=\mathrm{O}\left( k^{3} \right) $.

\section*{Exercise 7.113 Derive coefficients of LMMs.}

I wrote a cpp program to perform the calculation for rational number. The results are stored in file named "LMM.txt".
We can calculate that the coefficients of LMMs are

\begin{tabular}{|c| c| c| c| c| c| c|}
	\hline
\multicolumn{7}{|c|}{ABM}                  \\
\hline
$s$ & $p$ & $\beta_s$ & $\beta_{s-1}$ & $\beta_{s_2}$ & $\beta_{s-3}$ & $\beta_{s-4}$\\
\hline
$1$ & $1$ & $0$ & $1$ & & & \\
\hline
$2$  &  $2$ & $0$ & $3 /2$ & $-1 /2$ & & \\
\hline
$3$ & $3$ &  $0$ &  $23 /12$ &  $-4 /3$ &  $5 /12$ &\\
\hline
$4$ &  $4$ &  $0$ &  $55 /24$ &  $-59 /24$ &  $37 /24$& $-3 .8$\\
\hline
\end{tabular}

\begin{tabular}{|c|c|c|c|c|c|c|}
	\hline
	\multicolumn{7}{|c|}{AMM}\\
	\hline
	$s$ & $p$ & $\beta_s$ & $\beta_{s-1}$ & $\beta_{s_2}$ & $\beta_{s-3}$ & $\beta_{s-4}$\\
	\hline
	$1$ &  $1$ & 1& & & &\\
	\hline
	$1$ &$2$& $1 /2$ &  $1 /2$& & &\\
	\hline
	$2$ &  $3$ &  $5 /12$ &  $2 /3$ &  $-1 /12$ & &\\
	\hline
	$3$ &  $4$ &  $3 /8$ &  $19 /24$ &  $-5 /24$ &  $1 /24$ &\\
	\hline
	$4$ & $5$ &  $251 /720$ & $323 /360$ &  $-11 /30$ & $53 /360$ &  $-19 /720$\\
	\hline
\end{tabular}

\begin{tabular}{|c|c|c|c|c|c|c|c|}
	\hline
	\multicolumn{8}{|c|}{BDF}\\
	\hline
	$s$& $p$& $\alpha_s$& $\alpha_{s-1}$&$\alpha_{s-2}$& $\alpha_{s-3}$& $\alpha_{s-4}$& $\beta_s$\\
	\hline
	$1$&  $1$&  $1$& $-1$&&&&$1$\\
	\hline
	$2$& $2$& $1$& $-4 /3$& $1 /3$&&& $2 /3$\\
	\hline
	$3$ &  $3$ &  $1$& $-18 11$& $9 /11$& $-2 /11$ &&$6 /11$\\ 
	\hline
	$4$& $4$& $1$& $-48 /25$ & $36 /25$& $-16 /25$ &$3 /25$& $12 /25$\\
	\hline
\end{tabular}
\section*{Exercise 7.118 Derive the third-order BDF's characteristic polynomials and verify that the order of accuracy is indeed 3.}

ByExercise 7.113 we know that the characteristic polynomials of the third-order BDF is
\begin{equation*}
	\begin{split}
		\rho\left( z \right)&=-\frac{2}{11}+\frac{9}{11}z-\frac{18}{11}z^{2}+z^{3}\\
		\sigma\left( z \right)&=\frac{6}{11}z^{3}\\ 
	\end{split}
\end{equation*}

So we can calculate its order of accuracy by Theorem 7.116
\begin{equation*}
	\begin{split}
		\frac{\rho\left( z \right) }{\sigma\left( z \right) }
		=&\frac{-2+9z-18z^2+11z^{3}}{6z^{3}}\\
		=&-\frac{1}{6}\left[ \ln \left( z-1+1 \right)  \right]'''-\frac{3}{2}\left[ \ln \left( z-1+1 \right)  \right]''
		-3\left( z-1+1 \right)' +\frac{11}{6}\\
		=&-\frac{1}{6}\left[ 2-6\left( z-1 \right)+12\left( z-1 \right)^2-20\left( z-1 \right)^{3}+30\left( z-1 \right)^{4}+ \mathrm{O\left( z-1 \right)^{5} }   \right]\\
		 &-\frac{3}{2}\left[ -1+2\left( z-1 \right)-3\left( z-1 \right)^{2}+4\left( z-1 \right)^{3}-5\left( z-1 \right)^{4} +\mathrm{O}\left( z-1 \right)^{5}     \right]\\
		 &-3\left[ 1-\left( z-1 \right)+\left( z-1 \right)^2-\left( z-1 \right)^{3}+\left( z-1 \right)^{4}+ \mathrm{O}\left( z-1 \right)^{5}     \right]+\frac{11}{6}\\
		=&0+\left( z-1 \right)-\frac{1}{2}\left( z-1 \right)^2+\frac{1}{3}\left( z-1 \right)^{3}-\frac{1}{2}\left( z-1 \right)^{4}+\mathrm{O}\left( z-1 \right)^{5}\\
	\end{split}
\end{equation*}

So that the third-order BDF has order 3 with error constant $-\frac{3}{4}$.

\section*{Exercise 7.119}

\subsection*{Necessity.}
For a given s-step LMM with order of accuracy $p$, applying it to an ODE $u_t=q\left( t \right) $.
If $q$ is a polynomial with degree $d$ that satisfies $d<p$, we have $\forall n>d$, $u_{t^{n}}\left( t_n \right)=0 $.
Thus we have
\[
	\mathcal{L}u\left( t_n \right)=\sum_{i=0}^{\infty}C_ik^{i}u_{t^{i}}\left( t_n \right) 
	\sum_{i=0}^{d}C_ik^{i}u_{t^{i}}\left( t_n \right) =\mathrm{O}\left( k^{d} \right) 
.\] 
As the given LMM has order of accuracy p, we know $C_0=\ldots=C_d=0$.
Thus $\mathcal{L}u\left( t_n \right)=0 $, which means that the one-step error is zero. 
So all $u\left( t_n \right) $ calculated from exact numerical initial data are exact solution for $u_t=q\left( t \right) $.

If the degree of $q$ satisfies $d=p$, similarly we have 
 \[
	 \mathcal{L}u\left( t_n \right)=\sum_{i=0}^{p}C_ik^{i}u_{t^{i}}\left( t_n \right)=C_pk^{p}u_{t^{p}}\left( t_n \right) \neq 0  
.\] 
Thus $u\left( t_n \right) $ are not exact results as there exists one-step error.

\subsection*{Sufficiency.}
If for all polynomial $q$ with degree  $d<p$, the ODE $u_t=q\left( t \right) $ will get exact results with the given LMM. 
We can choose $q_i=x^{i}$. They all get exact results if $i\in\{0\ldots p-1\}$. 
Then we get a linear equations with $p$ unknowns.
 \begin{equation*}
	\begin{split}
		\mathcal{L}q_i\left( t_0 \right)=\sum_{j=0}^{i}C_jk^{j}u_{t^{j}}\left( t_0 \right)=0 \quad i\in\{0,\ldots,p-1\}  
	\end{split}
\end{equation*}
The coefficient matrix is nonsingular as it a lower triangular matrix with diagonal elements nonzero. 
So we can easily calculate that $C_0=C_1=\ldots=C_{p-1}=0$. 

Then we take $q$ the polynomial with degree  $p$ that cannot get exact results by the given LMM. We have  
 \[
	 \mathcal{L}q\left( t_n \right)=C_pk^{p}u_{t^{p}}\left( t_0 \right)\neq 0  
.\] 
Thus $C_p\neq 0$. So we knows that the given LMM has order of accuracy $p$.


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
